This invention relates to an error-correcting decoder for use as a counterpart of an error-correction encoder.
In the manner which will later be described more in detail, an error-correction encoder is for use in encoding a sequence of original information symbols into a sequence of original code symbols. For this purpose, a sequence of original redundancy symbols is produced from the original information symbol sequence in accordance with a predetermined rule and added to the original information symbol sequence to produce the original code symbol sequence. Each redundancy symbol may consist of only one bit, in which event it is often the case to refer to the redundancy symbol as a redundancy bit. The original code symbol sequence is whichever of a bit-series and a bit-parallel sequence and is either transmitted to a transmission channel or route or stored in a storage medium.
Either transmitted through the transmission channel or reproduced from the storage medium, the original code symbol sequence is supplied to a counterpart error-correcting decoder as an input sequence of received code symbols. When compared with the original code symbol sequence, the input sequence generally includes errors here and there mainly due to noise in the transmission channel or to physical defects of the storage medium. Regardless of presence and absence of the errors, it is possible to understand that the received code symbols are in correspondence to the respective original code symbols. The decoder is for producing a reproduction of the original information symbol sequence with the errors automatically corrected.
Such an error-correcting decoder is preferably a sequential error-correcting decoder. In the sequential error-correcting decoder, a sequential decode controller executes a sequential decoding algorithm on the input sequence to produce a local sequence of presumed or judged information symbols which are presumed for the respective original information symbols. An encoder replica is operable like the encoder and encodes the local sequence into a replica output sequence of presumed code symbols. To this end, the encoder replica produces a sequence of presumed redundancy symbols in response to the local sequence in accordance with the predetermined rule. When used together, the presumed information symbol sequence and the presumed redundancy symbol sequence provide the presumed code symbol sequence. Responsive to the input and the replica output sequences, a likelihood calculator calculates likelihoods which the presumed code symbols have relative to the respective received code symbols. The likelihood calculator thereby produces a likelihood signal which represents the likelihoods.
The likelihood signal is fed back to the sequential decode controller and is used in executing the sequential decoding algorithm. In this manner, the sequential decoding algorithm is executed according to a trial and error scheme to automatically correct the errors and thereby to make the encoder replica produce the presumed information symbol sequence as the reproduction of the original information symbol sequence. In order to carry out the trial and error scheme, at least one buffer is used in the decoder in the manner described in U.S. patent application Ser. No. 099,801 filed Sept. 22, 1987, by the present applicant (EPC patent application No. 87 1137 78.2 filed Sept.21, 1987) with reference to the drawing figures of that patent application. Inasmuch as the buffers have a limited capacity, buffer overflow is inevitable.
It is to be noted that the encoder internal state which is variable from time to time. The encoder replica has a replica internal state which varies in synchronism with the encoder internal state in a steady state of operation of the decoder. When the buffer overflow takes place, the replica internal state becomes out of synchronism with the encoder internal state. This makes it impossible for the decoder to produce the reproduction of the original information symbol sequence. It is therefore very desirable to deal with the buffer overflow to rapidly recover the steady state of operation.
Various methods of dealing with the buffer overflow are already known. Typically, the methods are the "guess-and-restart" technique and the blocked data technique described in a book jointly written by George C. Clark, Jr., and J. Bibb Cain under the title of "Error-Correction Coding for Digital Communications" and first published 1981 by Plenum Press, New York and London, particularly from page 316 to page 318 of the book.
According to the guess-and-restart technique, the input sequence is read into the buffer with a predetermined length omitted when the buffer overflow takes place. With a space thereby formed in the buffer, the replica internal state is initialized by using hard decisions of the received code symbols as the presumed code symbols. This may or may not put the replica internal state into synchronism with the encoder internal state. If the synchronism is not achieved by once initializing the replica internal state, the replica internal state must repeatedly be initialized with a space again formed in the buffer. When the transmission channel is used, the synchronism would have to be again and again initialized upon occurrence of burst errors. Even when the storage medium is used, it will take a long time to reach the steady state of operation of the decoder.
According to the blocked data technique, the original information symbol sequence is block in the encoder into an intermittent succession of blocks with a unique word interposed between each pair of successive blocks. In the decoder, the input sequence is read into the buffer with a predetermined number of blocks omitted when the buffer overflow takes plane. The replica internal state is initialized so as to be coincident with the unique word. This may shorten the time necessary for achieving the synchronism. Use of the unique words, however, reduces an amount of information which is either transmitted or stored. Moreover, block synchronism must be established between the encoder and the decoder. This is very difficult in a truck transmission channel. It is necessary on the other hand in the present-day information-intensitive social system, into which electronic digital computers and electrical and optical communication system are merged, to deal with a great amount of information at a high speed with the information protected against any errors and without the block synchronism.